#include"tree.h"
#include"Queue.h"

BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
    if (*pi >= n || a[*pi] == NULL||a[*pi]=='#'||a[*pi]=='\0')
    {
        (*pi)++;
        return NULL;
    }
    BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
    if (newnode == NULL)
    {
        perror("malloc fail");
        exit(1);
    }
    newnode->data = a[*pi];
    (*pi)++;
    newnode->left = BinaryTreeCreate(a, n, pi);
    newnode->right = BinaryTreeCreate(a, n, pi);
    return newnode;
}

void BinaryTreeDestory(BTNode** root)
{
    if (*root == NULL)
    {
        return;
    }
    BinaryTreeDestory(&((*root)->left));
    BinaryTreeDestory(&((*root)->right));
    free(*root);
    *root = NULL;
}

int BinaryTreeSize(BTNode* root)
{
    if (root==NULL)
    {
        return 0;
    }
    return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

int BinaryTreeLeafSize(BTNode* root)
{
    if (root == NULL)
    {
        return 0;
    }
    if (root->left == NULL && root->right == NULL)
    {
        return 1;
    }
    return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

int BinaryTreeLevelKSize(BTNode* root, int k)
{
    if (root == NULL)
    {
        return 0;
    }
    if (k == 1)
    {
        return 1;
    }
    return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
    if (root == NULL)
    {
        return NULL;
    }
    if (root->data == x)
    {
        return root;
    }
    BTNode* leftfind = BinaryTreeFind(root->left, x);
    if (leftfind)
    {
        return leftfind;
    }
    BTNode* rightfind = BinaryTreeFind(root->right, x);
    if (rightfind)
    {
        return rightfind;
    }
    return NULL;
}

void BinaryTreePrevOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }
    printf("%c ", root->data);
    BinaryTreePrevOrder(root->left);
    BinaryTreePrevOrder(root->right);
}

void BinaryTreeInOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }
    BinaryTreeInOrder(root->left);
    printf("%c ", root->data);
    BinaryTreeInOrder(root->right);
}

void BinaryTreePostOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }
    BinaryTreePostOrder(root->left);
    BinaryTreePostOrder(root->right);
    printf("%c ", root->data);
}

void BinaryTreeLevelOrder(BTNode* root)
{
    Queue q;
    QueueInit(&q);
    QueuePush(&q, root);
    while (!QueueEmpty(&q))
    {
        BTNode* top = QueueFront(&q);
        QueuePop(&q);
        printf("%c ", top->data);
        if (top->left)
            QueuePush(&q,top->left);
        if (top->right)
            QueuePush(&q,top->right);
    }
    QueueDestroy(&q);
}
bool BinaryTreeComplete(BTNode* root)
{
    Queue q;
    QueueInit(&q);
    QueuePush(&q, root);
    while (!QueueEmpty(&q))
    {
        BTNode* top = QueueFront(&q);
        QueuePop(&q);
        if (top == NULL)
        {
            break;
        }
        QueuePush(&q, top->left);
        QueuePush(&q, top->right);
    }
    while (!QueueEmpty(&q))
    {
        BTNode* top = QueueFront(&q);
        QueuePop(&q);
        if (top != NULL)
        {
            QueueDestroy(&q);
            return false;
        }
    }
    QueueDestroy(&q);
    return true;
}